package offer;

public class  Offer43 {

    public int countDigitOne1(int n) {

        if (n<=9){
            return 1;
        }
        int count=1;
        for (int i =10 ; i <=n; i++) {
            int tmp=i;
            while (tmp!=0){
                if (tmp%10==1){
                    count++;
                }
                tmp/=10;
            }
        }

        return  count;
    }



    public int countDigitOne(int n) {
        if (n < 1) {
            return 0;
        }
        // 高位
        int high = n;
        // 低位
        int low = 0;
        // 1出现的总次数
        int total = 0;
        // 当前位数，比如个位时为1，十位时为10，百位时为100
        int digit = 1;
        while (high != 0) {
            // 当前位上的数字
            int cur = high % 10;
            // 剩下的高位
            high = high / 10;
            // 如果当前位上的数字是0
            if (cur == 0) {
                // 只加上高位对应
                total += high * digit;
            }
            // 如果当前位上的数字是1
            else if (cur == 1) {
                // 加上高位对应的数字，和低位的所有，再加1(它本身)。
                // 比如10，虽然低位是0，但本身还有1
                total += high * digit + low + 1;
            }
            // 如果当前位上的数字大于1
            else {
                // 那么高位+1
                total += (high + 1) * digit;
            }

            // 低位
            low += cur * digit;
            // 进入下一位
            digit = digit * 10;
        }

        return total;
    }



    public static void main(String[] args) {
        Offer43 offer43 = new Offer43();
        System.out.println(offer43.countDigitOne(3210));

    }



}
